import random


def quick_sort(arr, lo, high):
    if lo < high:
        # 选取一个标准
        mid = arr[lo]
        i = lo
        j = high

        while i < j:
            # 这里等于符号必须添加
            while i < j and arr[j] >= mid:
                j -= 1
            arr[i] = arr[j]
            # 这里等于符号必须添加
            while i < j and arr[i] <= mid:
                i += 1
            arr[j] = arr[i]

        arr[i] = mid

        quick_sort(arr, lo, i-1)
        quick_sort(arr, i+1, high)

    return arr

        

def shuffle(arr):
    n = len(arr)
    for i in range(n):
        index_random = random.randint(0, i)
        arr[i], arr[index_random] = arr[index_random], arr[i]


if __name__ == "__main__":
    for _ in range(10000000):
        n = random.randint(5, 10)
        # 随机n次
        arr = []
        for i in range(n):
            arr.append(random.randint(0, 10))

        t = list(arr)
        t.sort()
        quick_sort(arr, 0, n-1)
        if arr != t:
            print('*' * 10)
